#!/usr/bin/env python
# -*- indent-tabs-mode: nil; tab-width: 4; coding: utf-8 -*-
# vi: set ts=4 sts=4 sw=4 set smarttab set expandtab
#http://www.careercup.com/question?id=9332640
#Facebook interview question
"""
Really like the linear solution of this problem. You have an array of 0s and 1s and you want to output all the intervals (i, j) where the number of 0s and numbers of 1s are equal.

Example

pos = 0 1 2 3 4 5 6 7 8
0 1 0 0 1 1 1 1 0

One interval is (0, 1) because there the number of 0 and 1 are equal. There are many other intervals, find all of them in linear time.
"""
from collections import defaultdict
def get_equal_intervals(arr):
    sums = defaultdict(list)
    sums[0.5].append(-1)
    sum_value = 0
    result = []
    for i in range(0, len(arr)):
        sum_value += arr[i]
        temp = sum_value - float(i) / 2
        if temp in sums:
            for interval_start in sums[temp]:
                result.append((interval_start + 1, i))
        sums[temp].append(i)
    return result

if __name__ == '__main__':
    from utils import *
    arr = random_arr(10, 0, 1)
    print arr
    print get_equal_intervals(arr)
